package com.mj.listen2._01_排序.cmp;

/**
 * 快速排序
 * 思想：
 * 使用分治法。
 * 定义left，right指针，以数组的最后一个元素为参照物，left指向当前要排序组的第0个位置，right指向当前要排序数组的参照物的前一个数据（即倒数第二个位置）
 * left从左往右找，当找到第一个比参照物大的数据，right从右往左找，找到第一个比参照物小的数据。如果left和right没有交叉（left<right），交换两个位置
 * 的数据。若出现了交叉（left>=right）让left位置数据跟参照物交换；然后把left作为中间位置，此时数组被分成了两瓣，左边的数据都比参照物小，右边的数据
 * 都比参照物大。然后再对两边的数据重复操作。
 */
public class _07_QuickSort1<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        quickSort(array, 0, array.length - 1);
    }

    private void quickSort(T[] arr, int start, int end) {
        if (start >= end) {
            // 只有一个元素
            return;
        }

        int middle = findMiddle(arr, start, end);
        // 对 [0,middle - 1]位置进行快速排序
        quickSort(arr, 0, middle - 1);
        // 对 [middle + 1,end]位置进行快速排序
        quickSort(arr, middle + 1, end);
    }

    // 找到快速排序的中间索引
    private int findMiddle(T[] arr, int start, int end) {
        int left = start;
        int right = end - 1;
        // 参照物
        T temp = arr[end];

        // 开始查找
        while (true) {
            // left从左往右找，当找到第一个比参照物大的数据，
            while (left < end && cmp(arr[left], temp) <= 0) {
                left++;
            }

            // 如果left到了数组末尾了，说明末尾索引左侧的数据全部都比末尾索引值要小。直接跳出循环即可
            if (left == end) {
                break;
            }

            // right从右往左找，找到第一个比参照物小的数据
            while (right > start && cmp(arr[right], temp) >= 0) {
                right--;
            }

            // 扫描完毕，判断left与right是否有过交叉
            if (left < right) {
                // 没有交叉，交换left和right索引位置的数据
                swap(left, right);
            } else {
                // 出现交叉，让left索引与参照物索引数据交换
                swap(left, end);
                // 找到了中间位置，left指针指向的位置就是
                break;
            }
        }

        return left;
    }
}
